package 数据结构.树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-27
 */
public class JZ32从上往下打印二叉树 {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root==null) {
            return list;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            TreeNode node = q.poll();
            list.add(node.val);
            if(node.left!=null){
                q.offer(node.left);
            }
            if(node.right!=null)
                q.offer(node.right);
        }
        return list;
    }

    //递归
    public ArrayList<Integer> PrintFromTopToBottom2(TreeNode root) {
        ArrayList<Integer> res = new ArrayList();
        ArrayList<ArrayList<Integer> > temp = new ArrayList<ArrayList<Integer> >();
        if(root == null)
            //如果是空，则直接返回
            return res;
        //递归层次遍历
        traverse(root, temp, 1);
        //送入一维数组
        for(int i = 0; i < temp.size(); i++)
            for(int j = 0; j < temp.get(i).size(); j++)
                res.add(temp.get(i).get(j));
        return res;
    }

    void traverse(TreeNode root, ArrayList<ArrayList<Integer> > res, int depth) {
        if(root!=null){
            if(res.size()<depth){
                ArrayList<Integer> row = new ArrayList();
                res.add(row);
                row.add(root.val);
            }else{
                ArrayList<Integer> row = res.get(depth - 1);
                row.add(root.val);
            }
        }else{
            return;
        }
        traverse(root.left,res,depth+1);
        traverse(root.right,res,depth+1);

    }
}
